package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Project : algorithm-learning-java
 * @Package : leetcode
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/1/15 16:33
 */
public class Q0120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 1) return triangle.get(0).get(0);
        int[][] f = new int[triangle.size()][triangle.size()];
        f[0][0] = triangle.get(0).get(0);
        int res = 0x3f3f3f3f;
        for (int i = 1; i < f.length; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    f[i][j] = f[i - 1][j];
                } else if (j == i) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = Math.min(f[i - 1][j], f[i - 1][j - 1]);
                }
                f[i][j] += triangle.get(i).get(j);
                if (i == f.length - 1) res = Math.min(res, f[i][j]);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Q0120 sl = new Q0120();
    }
}
